/LMAR=0/XLINE=4/USET=29␈↓ α←␈↓␈↓1.1␈↓ λ|Introduction     5␈↓

␈↓"β␈↓ α←␈↓will␈α∂write␈α∂<object>;␈α∂when␈α∂we␈α∂are␈α∂talking␈α∂about␈α∂the␈α∂abstract␈α∂object␈α⊂we␈α∂will
␈↓ α←␈↓write ␈↓<object>␈↓. For example ␈↓<numeral>␈↓ is the class of natural numbers.
␈↓"β␈↓ α←␈↓␈↓ β'What␈α
should␈α∞be␈α
remembered␈α∞from␈α
the␈α
discussion␈α∞in␈α
this␈α∞section?␈α
 We
␈↓ α←␈↓need␈αprecise␈αways␈αof␈αdescribing␈αthe␈αelements␈αof␈αour␈αstudy␈αon␈αdata␈αstructures.
␈↓ α←␈↓We␈α∂have␈α∂seen␈α∞that␈α∂inductive␈α∂definitions␈α∂are␈α∞a␈α∂powerful␈α∂way␈α∂of␈α∞describing
␈↓ α←␈↓sets␈α∀of␈α∀objects.␈α∀We␈α∀have␈α∪seen␈α∀a␈α∀variant␈α∀of␈α∀inductive␈α∀definitions␈α∪called
␈↓ α←␈↓Backus-Naur␈α∂Form␈α⊂equations.␈α∂We␈α⊂will␈α∂use␈α∂BNF␈α⊂equations␈α∂to␈α⊂describe␈α∂the
␈↓ α←␈↓syntax of our data structures and our language.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αhave␈αalso␈αintroduced␈αthe␈αdifference␈αbetween␈αan␈αabstract␈αobject␈αand
␈↓ α←␈↓a␈α∂representation␈α∞for␈α∂that␈α∂object.␈α∞ This␈α∂distinction␈α∂has␈α∞been␈α∂well␈α∂studied␈α∞in
␈↓ α←␈↓philosophy␈α∪and␈α∪mathematics,␈α∪and␈α∪we␈α∀will␈α∪see␈α∪that␈α∪this␈α∪idea␈α∀has␈α∪strong
␈↓ α←␈↓consequences␈α∞for␈α∞the␈α
field␈α∞of␈α∞programming␈α
and␈α∞computer␈α∞science.␈α
 Abstract
␈↓ α←␈↓objects and their representations will play crucial roles in this text.


␈↓"β␈↓ α←␈↓␈↓ βy␈↓↓1.2  Symbolic Expressions: Abstract Data Structures␈↓

␈↓"β␈↓ α←␈↓We␈α∞wish␈α∞to␈α
show␈α∞that␈α∞the␈α∞use␈α
of␈α∞abstraction␈α∞will␈α
benefit␈α∞the␈α∞study␈α∞of␈α
data
␈↓ α←␈↓structures␈α∞and␈α∞LISP.␈α∞ To␈α∂begin␈α∞our␈α∞study␈α∞we␈α∞should␈α∂therefore␈α∞characterize
␈↓ α←␈↓the␈αdomain␈αof␈αLISP␈αdata␈αstructures␈αin␈αa␈αmanner␈αsimilar␈αto␈αwhat␈αwe␈α
did␈αfor
␈↓ α←␈↓numbers.
␈↓"β␈↓ α←␈↓␈↓ β'Our␈α→objects␈α→are␈α→called␈α→␈↓↓Symbolic␈α→Expressions␈↓.␈α→ Our␈α→domain␈α→of
␈↓ α←␈↓Symbolic␈α∩Expressions␈α∩is␈α∩named␈α∩␈↓<sexpr>␈↓.␈α∩ Symbolic␈α∩expressions␈α∩are␈α⊃also
␈↓ α←␈↓known as ␈↓↓S-expressions␈↓ or ␈↓↓S-exprs␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α
set␈α∞of␈α
symbolic␈α
expressions␈α∞is␈α
defined␈α
inductively␈α∞over␈α
a␈α∞base␈α
set
␈↓ α←␈↓named␈α
␈↓<atom>␈↓.␈α
The␈α
set␈α
␈↓<atom>␈↓␈α
can␈α
itself␈α
be␈α
defined␈α
inductively.␈α
We␈α
give␈α
a
␈↓ α←␈↓set␈α∃of␈α∀BNF␈α∃equations␈α∀for␈α∃elements␈α∀of␈α∃<atom>␈α∀below,␈α∃but␈α∃the␈α∀essential
␈↓ α←␈↓character␈αof␈αthe␈αdomain␈αis␈αthat␈αit␈αrepresents␈αtwo␈αkinds␈αof␈αobjects:␈αthe␈α␈↓↓literal
␈↓ α←␈↓↓atoms␈↓ and the integers.  The elements of ␈↓<atom>␈↓ are called ␈↓↓atoms␈↓.
␈↓"∀␈↓ α←␈↓<atom>␈↓ ∧7:: = <literal atom> | <numeral> | -<numeral>
␈↓"	␈↓ α←␈↓<literal atom>␈↓ ∧7:: = <atom letter>
␈↓"β␈↓ α←␈↓␈↓ ∧7:: = <literal atom><atom letter>
␈↓"β␈↓ α←␈↓␈↓ ∧7:: = <literal atom><digit>
␈↓"	␈↓ α←␈↓<numeral>␈↓ ∧7:: = <digit> | <numeral><digit>
␈↓"	␈↓ α←␈↓<atom letter>␈↓ ∧7:: =␈↓α A | B | C ... | Z␈↓ ␈↓π 3␈↓
␈↓"	␈↓ α←␈↓<digit>␈↓ ∧7:: = ␈↓α0 | 1 | 2 ... | 9␈↓
␈↓"∀␈↓ α←␈↓A␈α<literal␈α
atom>␈αis␈αtherefore␈α
a␈αstring␈αof␈α
uppercase␈αletters␈αand␈α
digits,␈αsubject
␈↓ α←␈↓to the provision that the ␈↓¬first␈↓ character in the atom be a letter.


␈↓"β␈↓ α←␈↓________________
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 3␈↓We use ellipses here as a convienient abbreviation.
␈¬␈↓ α←␈↓␈↓3.1␈↓ λ↑Introduction     101␈↓

␈↓"β␈↓ α←␈↓about␈α↔call-by-name␈α⊗and␈α↔other␈α⊗styles␈α↔of␈α⊗evaluation␈α↔in␈α↔Section 3.13␈α⊗and
␈↓ α←␈↓Section 4.9.  Most of this chapter will be restricted to call-by-value.
␈↓"β␈↓ α←␈↓␈↓ β'If␈αyou␈αlook␈αat␈α
the␈αstructure␈αof␈α␈↓αvalue␈↓λ''␈↓␈α
and␈α␈↓αapply␈↓λ'␈↓␈αbeginning␈αon␈α
page 86
␈↓ α←␈↓you␈α
will␈αsee␈α
that␈αthey␈α
encode␈αa␈α
call-by-value␈αstrategy␈α
and␈αhave␈α
the␈αfollowng
␈↓ α←␈↓interpretation:

␈↓"λ␈↓ α←␈↓␈↓↓1.␈↓  If␈α∂the␈α∂expression␈α∂is␈α∂a␈α∂constant␈α∞then␈α∂the␈α∂value␈α∂of␈α∂the␈α∂expression␈α∂is␈α∞that
␈↓ α←␈↓␈↓ β∂constant.  (The value of ␈↓α3␈↓ is ␈↓α3␈↓).␈↓π 5␈↓
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓  If␈αthe␈αexpression␈αis␈αa␈αvariable␈αthen␈αsee␈αwhat␈αthe␈αcurrent␈αvalue␈αassociated
␈↓ α←␈↓␈↓ β∂with␈α⊗that␈α⊗variable␈α↔is.␈α⊗Within␈α⊗the␈α↔evaluation␈α⊗of,␈α⊗say,␈α↔␈↓αf[3;4]␈↓␈α⊗where
␈↓ α←␈↓␈↓ β∂␈↓αf[x;y] <= x␈↓π2␈↓α + y ␈↓the current value of the variable ␈↓αx␈↓ is ␈↓α3␈↓.
␈↓"	␈↓ α←␈↓␈↓↓3.␈↓  The␈α∩only␈α∩other␈α∩kind␈α∩of␈α∩arithmetic␈α∩expression␈α∩that␈α∩we␈α∩can␈α∩have␈α∩is␈α⊃a
␈↓ α←␈↓␈↓ β∂function␈α
name␈α
followed␈α
by␈α
arguments,␈α
for␈α
example␈α
␈↓αf[3;4]␈↓.␈α
 In␈α
this␈αcase␈α
we
␈↓ α←␈↓␈↓ β∂first␈α∩evaluate␈α∩the␈α∩arguments␈α∩␈↓π 6␈↓␈α∩and␈α∩then␈α∩apply␈α∩the␈α∩definition␈α∩of␈α∩the
␈↓ α←␈↓␈↓ β∂function␈α∩to␈α∩those␈α⊃evaluated␈α∩arguments.␈α∩ When␈α⊃we␈α∩apply␈α∩the␈α⊃function
␈↓ α←␈↓␈↓ β∂definition␈αto␈αthe␈αevaluated␈αarguments␈αwe␈αassociate␈αthe␈αformal␈αparameters
␈↓ α←␈↓␈↓ β∂of␈α
the␈αdefinition␈α
with␈α
the␈αvalues␈α
of␈α
the␈αactual␈α
parameters.␈α
 This␈αprocess
␈↓ α←␈↓␈↓ β∂of␈α∞associating␈α∞parameters␈α∞is␈α∞called␈α∞␈↓↓binding␈↓␈α∞and␈α∞simulates␈α∞some␈α∞form␈α
of
␈↓ α←␈↓␈↓ β∂substitution.␈α
 We␈α
then␈α
evaluate␈α
the␈α
body␈α
of␈α
the␈α
function␈α
using␈α
this␈α
new
␈↓ α←␈↓␈↓ β∂environment.␈α∂ Notice␈α∞that␈α∂we␈α∂do␈α∞␈↓¬not␈↓␈α∂explicitly␈α∞substitute␈α∂the␈α∂values␈α∞for
␈↓ α←␈↓␈↓ β∂the␈α∞variables␈α∞which␈α∞appear␈α∞in␈α∞an␈α∞expression.␈α∞We␈α∞␈↓¬simulate␈↓␈α∞substitutions
␈↓ α←␈↓␈↓ β∂by table lookup.
␈↓"∀␈↓ α←␈↓␈↓ β'We␈αwant␈αto␈αapply␈αthis␈αtreatment␈αof␈αevaluation␈αto␈αLISP␈αexpressions.␈α If
␈↓ α←␈↓the␈α∞LISP␈α∞expression␈α∞is␈α∞a␈α∞constant,␈α
then␈α∞the␈α∞value␈α∞of␈α∞the␈α∞expression␈α∞is␈α
that
␈↓ α←␈↓constant.␈α The␈α
constants␈αof␈αLISP␈α
are␈αthe␈αS-exprs.␈α
Thus␈αthe␈αvalue␈α
of␈α␈↓α(A . B)␈↓
␈↓ α←␈↓is␈α
␈↓α(A . B)␈↓,␈α
just␈αlike␈α
the␈α
value␈αof␈α
␈↓α3␈↓␈α
is␈α␈↓α3␈↓.␈α
 Variables␈α
and␈αfunctional␈α
applications
␈↓ α←␈↓appear␈αin␈αLISP␈αand␈αare␈αhandled␈αsimilarly␈αto␈α␈↓↓2␈↓␈αand␈α␈↓↓3␈↓␈αabove.␈α The␈α
additional
␈↓ α←␈↓artifact␈αof␈αLISP␈αis␈αthe␈αconditional␈αexpression.␈αBut␈αits␈αevaluation␈αcan␈αalso␈αbe
␈↓ α←␈↓precisely specified. We did so on page 20.
␈↓"β␈↓ α←␈↓␈↓ β'In␈α∪more␈α∩specific␈α∪detail,␈α∩here␈α∪is␈α∩some␈α∪of␈α∩the␈α∪structure␈α∩of␈α∪the␈α∩LISP
␈↓ α←␈↓evaluation mechanism:

␈↓"λ␈↓ α←␈↓␈↓↓1.␈↓  If␈α⊃the␈α⊂expression␈α⊃to␈α⊃be␈α⊂evaluated␈α⊃is␈α⊂a␈α⊃constant␈α⊃then␈α⊂the␈α⊃value␈α⊃is␈α⊂that
␈↓ α←␈↓␈↓ β∂constant.
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓  If the expression is a variable find its value in the current environment.
␈↓"	␈↓ α←␈↓␈↓↓3.␈↓  If␈α∀the␈α∪expression␈α∀is␈α∪a␈α∀conditional␈α∪expression␈α∀then␈α∪it␈α∀is␈α∪of␈α∀the␈α∪form
␈↓ α←␈↓␈↓ β∂␈↓α[␈↓↓p␈↓β1␈↓α → ␈↓↓e␈↓β1␈↓α; ␈↓↓p␈↓β2␈↓α → ␈↓↓e␈↓β2␈↓α; ... ;␈↓↓p␈↓βn␈↓α → ␈↓↓e␈↓βn␈↓α]␈↓.␈α Evaluate␈α
it␈αusing␈α
the␈αsemantics␈αdefined␈α
on
␈↓ α←␈↓␈↓ β∂page 20.


␈↓"β␈↓ α←␈↓________________
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 5␈↓We␈α∪are␈α∀ignoring␈α∪the␈α∀distinction␈α∪between␈α∪the␈α∀␈↓¬numeral␈↓␈α∪␈↓α3␈↓␈α∀and␈α∪the
␈↓ α←␈↓␈↓¬number␈↓α 3.␈↓
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 6␈↓Here we are using the evaluation process recursively.
␈¬α␈↓ α←␈↓␈↓3.6␈↓ λ-Examples of ␈↓αeval␈↓     127␈↓α


␈↓"β␈↓ α←␈↓α␈↓ βK|   x : (A . B)␈↓ ¬;|␈↓ εK|       x : A␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK|   y : (A . B)␈↓ ¬;|␈↓ εK|       y : A␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK| x : ((A . B) . C)␈↓ ¬;|  ==>␈↓ εK|    x : (A . B)␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK| y : ((A . B) . D)␈↓ ¬;|␈↓ εK|    y : (A . B)␈↓ λ;| ==>
␈↓"β␈↓ α←␈↓α␈↓ βK|equal : λ[[x;y] ... ]␈↓ ¬;|␈↓ εK| x : ((A . B) . C)␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK␈↓ ¬;␈↓ εK| y : ((A . B) . D)␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK␈↓ ¬;␈↓ εK|equal : λ[[x;y] ... ]␈↓ λ;|

␈↓"β␈↓ α←␈↓α␈↓ βK|       x : B␈↓ ¬;|␈↓ εK|        x : C␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK|       y : B␈↓ ¬;|␈↓ εK|        y : D␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK|    x : (A . B)␈↓ ¬;|␈↓ εK|  x : ((A . B) . C)␈↓ λ;| ==>
␈↓"β␈↓ α←␈↓α␈↓ βK|    y : (A . B)␈↓ ¬;| ==>␈↓ εK|  y : ((A . B) . D)␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK| x : ((A . B) . C)␈↓ ¬;|␈↓ εK|equal : λ[[x;y] ... ]␈↓ λ;|
␈↓"β␈↓ α←␈↓α␈↓ βK| y : ((A . B). D)␈↓ ¬;|
␈↓"β␈↓ α←␈↓α␈↓ βK|equal : λ[[x;y] ... ]␈↓ ¬;|


␈↓"β␈↓ α←␈↓α␈↓ ¬[|equal : λ[[x;y] ... ] |
␈↓"∀␈↓ α←␈↓This␈α_degree␈α_of␈α_complexity␈α_is␈α_necessary,␈α_for␈α_while␈α_we␈α_are␈α_evaluating
␈↓ α←␈↓␈↓αequal[car[x];car[y]]␈↓,␈αwe␈αrebind␈α␈↓αx␈↓␈α
and␈α␈↓αy␈↓␈αbut␈αwe␈αmust␈α
save␈αthe␈αold␈αvalues␈α
of␈α␈↓αx␈↓
␈↓ α←␈↓and␈α∞␈↓αy␈↓␈α∞for␈α∞the␈α∞possible␈α∞evaluation␈α∞of␈α∞␈↓αequal[cdr[x];cdr[y]].␈↓␈α∞It␈α∞is␈α∞␈↓¬not␈↓␈α∂clear␈α∞that
␈↓ α←␈↓this␈αimplementation␈αis␈αoptimal.␈α
The␈αsearch␈αfor␈αthe␈αvalues␈α
of␈α␈↓αx␈↓␈αand␈α␈↓αy␈↓␈αis␈α
short,
␈↓ α←␈↓but␈α∞the␈α∞evaluation␈α∞of␈α∞any␈α
subexpressions␈α∞involving␈α∞␈↓αequal␈↓␈α∞must␈α∞retrieve␈α
the
␈↓ α←␈↓definition␈α∂of␈α∂␈↓αequal␈↓.␈α∂That␈α∞search␈α∂is␈α∂proportional␈α∂to␈α∞the␈α∂depth␈α∂of␈α∂the␈α∞initial
␈↓ α←␈↓arguments to ␈↓αequal␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'Before␈α
continuing,␈αwe␈α
should␈αexamine␈α
␈↓αeval␈↓␈αand␈α
␈↓αapply␈↓␈αto␈α
see␈α
how␈αthey
␈↓ α←␈↓compare␈α⊂with␈α∂our␈α⊂previous␈α⊂discussions␈α∂of␈α⊂LISP␈α∂evaluation.␈α⊂ The␈α⊂spirit␈α∂of
␈↓ α←␈↓call-by-value␈αand␈αconditional␈αexpression␈αevaluation␈αis␈αmaintained.␈α λ-binding
␈↓ α←␈↓seems␈α∂correct,␈α∂though␈α∂our␈α∂current␈α∂discussion␈α∂is␈α∂not␈α∂complete.␈α∂ At␈α⊂least␈α∂one
␈↓ α←␈↓preconception␈α
is␈α
not␈α∞maintained␈α
here.␈α
Recall␈α∞the␈α
discussion␈α
on␈α∞page 17.␈α
We
␈↓ α←␈↓wanted␈α
n-ary␈α
functions␈α
called␈α
with␈α
exactly␈α
n␈α
arguments.␈α
An␈α
examination␈α
of
␈↓ α←␈↓the␈α∃structure␈α∃of␈α∃␈↓αeval␈↓␈α∃and␈α∃␈↓αapply␈↓␈α∀shows␈α∃that␈α∃if␈α∃a␈α∃function␈α∃expecting␈α∀␈↓¬n␈↓
␈↓ α←␈↓arguments␈α
is␈α∞presented␈α
with␈α∞fewer,␈α
then␈α∞the␈α
result␈α∞is␈α
undefined;␈α∞but␈α
if␈α∞it␈α
is
␈↓ α←␈↓given␈α
␈↓¬more␈↓␈α
arguments␈α
than␈α
necessary␈α
then␈α
the␈α
calculation␈α
is␈α
performed.␈α
For
␈↓ α←␈↓example:
␈↓"∀␈↓ α←␈↓αeval[(CONS (QUOTE A) (QUOTE B) (QUOTE C));NIL]
␈↓"β␈↓ α←␈↓α␈↓ ∧7␈↓reduces to ␈↓α  eval[(CONS (QUOTE A) (QUOTE B));NIL]
␈↓"β␈↓ α←␈↓α␈↓ ∧7␈↓reduces to ␈↓α (A . B)
␈↓"∀␈↓ α←␈↓␈↓ β'This␈α∞example␈α∞shows␈α∞one␈α∞of␈α∞the␈α
pitfalls␈α∞in␈α∞defining␈α∞a␈α∞language␈α∞by␈α
an
␈↓ α←␈↓evaluator.␈α
 If␈α
the␈α
intuitions␈α
of␈α
the␈α
language␈α
specifiers␈α
are␈α
faulty␈α
or␈α
incomplete
␈↓ α←␈↓then␈αeither␈αwe␈αmust␈αmaintain␈αthat␈αfaulty␈αjudgement,␈αor␈αwe␈αmust␈αlobby␈αfor␈αa
␈¬␈↓ α←␈↓␈↓192  Imperative Constructs in LISP␈↓ 
(4.2␈↓

␈↓"β␈↓ α←␈↓␈↓ β'Now␈α↔to␈α↔the␈α⊗problem␈α↔of␈α↔translating␈α⊗a␈α↔␈↓αprog␈↓␈α↔into␈α↔an␈α⊗S-expression
␈↓ α←␈↓representation: the construct,
␈↓"∀␈↓ α←␈↓␈↓ β'␈↓ ∧P␈↓αprog[[v␈↓β1␈↓α; ...; v␈↓βn␈↓α] ...  ]␈↓ will be translated to: 
␈↓"	␈↓ α←␈↓␈↓ β'␈↓ ¬E␈↓α(PROG(V1 ... VN) ...  )␈↓ 
␈↓"∀␈↓ α←␈↓The␈α⊃body␈α⊃of␈α⊃the␈α⊃␈↓αprog␈↓␈α⊃must␈α⊃be␈α⊃handled␈α⊃specially␈α⊃by␈α⊃a␈α⊃new␈α⊃piece␈α⊃of␈α⊂the
␈↓ α←␈↓evaluator since ␈↓αprog␈↓ is a special form.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αmust␈αalso␈αbe␈αcareful␈αabout␈αthe␈αinterpretation␈αof␈α←.␈α We␈αwill␈αwrite␈α␈↓αx
␈↓ α←␈↓α← y␈↓ in prefix form: ␈↓αsetq[x;y]␈↓. We will map this to:
␈↓"∀␈↓ α←␈↓␈↓ ε␈↓α(SETQ X Y) ␈↓
␈↓"β␈↓ α←␈↓The␈α∞assignment,␈α
␈↓αsetq␈↓,␈α∞is␈α∞also␈α
a␈α∞special␈α
form.␈α∞ For␈α∞if␈α
␈↓αx␈↓␈α∞and␈α
␈↓αy␈↓␈α∞have␈α∞values␈α
␈↓α2␈↓
␈↓ α←␈↓and␈α∞␈↓α3␈↓,␈α∞for␈α∞example,␈α∞then␈α∞the␈α∞call-by-value␈α∞interpretation␈α∞of␈α∂␈↓αsetq[x;y]␈↓␈α∞would
␈↓ α←␈↓say␈α∞␈↓αsetq[2;3]␈↓.␈α∞This␈α∞was␈α
not␈α∞our␈α∞intention.␈α∞ We␈α
want␈α∞to␈α∞evaluate␈α∞the␈α
second
␈↓ α←␈↓argument to ␈↓αsetq␈↓ while stopping the evaluation of the first argument.
␈↓"β␈↓ α←␈↓␈↓ β'LISP␈α
has␈αanother␈α
assignment-like␈α
operator␈αcalled␈α
␈↓αset␈↓.␈α
 Both␈αarguments
␈↓ α←␈↓of␈α⊃this␈α⊃binary␈α⊃operator␈α⊃are␈α⊃evaluated;␈α⊃the␈α⊃value␈α⊃of␈α⊃the␈α⊃first␈α⊃argument␈α⊂is
␈↓ α←␈↓expected␈α⊃to␈α⊃be␈α⊃a␈α⊃representation␈α⊃of␈α⊂a␈α⊃variable;␈α⊃that␈α⊃is,␈α⊃the␈α⊃first␈α⊂argument
␈↓ α←␈↓evaluates␈αto␈αa␈αliteral␈αatom.␈α The␈αsecond␈αargument␈αis␈αa␈αLISP␈αform␈αand␈αusing
␈↓ α←␈↓the␈αvalue␈αof␈αthat␈αform,␈αan␈αassignment␈αis␈αmade␈αto␈αthe␈αvariable␈αrepresented␈αby
␈↓ α←␈↓the first argument. Thus ␈↓αsetq[x;y]␈↓ is synonymous with ␈↓αset[quote[x];y]␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'As␈α∞a␈α∞more␈α∞complex␈α∞example,␈α∞consider␈α∞␈↓αset[z;␈α∞plus[x;1]]␈↓.␈α∞ If␈α∞the␈α
current
␈↓ α←␈↓value␈α∀of␈α∀variable␈α∀␈↓αz␈↓␈α∀is␈α∀an␈α∀identifier,␈α∀then␈α∀␈↓αset[z;␈α∀plus[x;1]]␈↓␈α∃makes␈α∀sense.
␈↓ α←␈↓Assume␈αthe␈αcurrent␈αvalue␈αof␈α
␈↓αz␈↓␈αis␈α␈↓αA␈↓;␈αand␈αassume␈α
the␈αcurrent␈αvalue␈αof␈α␈↓αx␈↓␈α
is␈α␈↓α2␈↓;
␈↓ α←␈↓since␈α␈↓αA␈↓␈αrepresents␈αthe␈αidentifier␈α␈↓αa␈↓,␈αthe␈αeffect␈αof␈αthe␈α␈↓αset␈↓␈αstatement␈αis␈αto␈αassign
␈↓ α←␈↓the␈α
value␈α␈↓α3␈↓␈α
to␈α
␈↓αa␈↓.␈α Normally␈α
when␈α
making␈αassignments,␈α
we␈α
want␈αto␈α
assign␈αto␈α
a
␈↓ α←␈↓␈↓¬name␈↓ and not a ␈↓¬value␈↓; thus we will tend to use the ␈↓αsetq␈↓ form.
␈↓"β␈↓ α←␈↓␈↓ β'Finally, here is a translation of the body of the ␈↓αprog␈↓ version of ␈↓αlength:␈↓ ␈↓α
␈↓"∀␈↓ α←␈↓α␈↓ β'(LAMBDA␈↓ ∧C(L)
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C(PROG (L1 C)
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C␈↓ ∧s(SETQ L1 L)
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C␈↓ ∧s(SETQ C 0)
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧CA␈↓ ∧s(COND ((NULL L1) (RETURN C)))
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C␈↓ ∧s(SETQ C (ADD1 C))
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C␈↓ ∧s(SETQ L1 (REST L1))
␈↓"β␈↓ α←␈↓α␈↓ β'␈↓ ∧C␈↓ ∧s(GO A) ))
␈↓"∀␈↓ α←␈↓α␈↓ β'␈↓ Now␈α
that␈α
assignment␈α
statements␈α
have␈α
been␈α
described,␈α
let's␈α
re-examine
␈↓ α←␈↓"<=".␈αWe␈αalready␈αknow␈α(page 147)␈αthat␈α"<="␈αdoes␈αmore␈αthan␈αsimply␈αassociate
␈↓ α←␈↓the␈α
right␈α
hand␈αside␈α
with␈α
a␈α
symbol␈αtable␈α
entry␈α
of␈α
the␈αleft␈α
hand␈α
side;␈α
it␈αmust
␈↓ α←␈↓also␈αassociate␈αan␈αenvironment␈α
with␈αthe␈αfunction␈αbody,␈αand␈α
this␈αenvironment
␈↓ α←␈↓is␈αto␈α
be␈αused␈α
for␈αaccessing␈α
non-local␈αvariables.␈α
This␈αoperation␈α
of␈αassociating
␈↓ α←␈↓environments is called forming the ␈↓↓closure␈↓. We thus might be tempted to say:
␈↓"∀␈↓ α←␈↓α␈↓ ∧Kf <= λ[[ ... ] ...] ␈↓is␈↓α  f ← function[λ[[ ...] ...] ]
␈↓"∀␈↓ α←␈↓Alas, this implementation is still not sufficient as we will see in Section 4.11.
␈¬␈↓ α←␈↓␈↓254  Static Structure␈↓ 
(5.4␈↓

␈↓"β␈↓ α←␈↓␈↓¬example␈↓␈α∂of␈α∂␈↓αcar␈↓,␈α⊂but␈α∂the␈α∂extraneous␈α∂details␈α⊂of␈α∂specific␈α∂addresses␈α⊂have␈α∂been
␈↓ α←␈↓stripped␈α∀away.␈α∪ We␈α∀will␈α∪use␈α∀such␈α∪diagrams␈α∀occasionally␈α∪when␈α∀they␈α∪will
␈↓ α←␈↓contribute to clarity.

␈↓"β␈↓ α←␈↓␈↓ ε≡␈↓↓Problem␈↓
␈↓"∀␈↓ α←␈↓␈↓ β'Give an AMBIT diagram for ␈↓αeq␈↓.


␈↓"β␈↓ α←␈↓␈↓ ∧Z␈↓↓5.5  A Few Programming Techniques␈↓

␈↓"β␈↓ α←␈↓There␈α∞are␈α∞a␈α
few␈α∞useful␈α∞and␈α
practical␈α∞LISP␈α∞programming␈α∞techniques␈α
which
␈↓ α←␈↓take␈α∞advantage␈α∞of␈α∞the␈α∞implementation.␈α∞ These␈α∞tricks␈α∞are␈α∞supported␈α∂in␈α∞most
␈↓ α←␈↓implementations␈α∞and␈α
are␈α∞useful␈α∞enough␈α
that␈α∞they␈α
should␈α∞be␈α∞documented␈α
as
␈↓ α←␈↓programming language features.
␈↓"	␈↓ α←␈↓␈↓↓1.␈↓␈αIn␈αmost␈αimplementations␈αof␈α␈↓αeq␈↓␈αthe␈αcheck␈αfor␈αatom-ness␈αis␈αsuppressed␈αand␈αa
␈↓ α←␈↓␈↓ β∂simple␈α⊃address␈α⊃comparison␈α∩is␈α⊃made.␈α⊃Non-atomic␈α⊃S-expressions␈α∩are␈α⊃not
␈↓ α←␈↓␈↓ β∂usually stored uniquely;␈↓π 7␈↓ Thus in most implementations
␈↓"∀␈↓ α←␈↓␈↓ βK␈↓αeq[(A . B);(A . B)]␈↓      is usually false, but
␈↓"	␈↓ α←␈↓␈↓ βK␈↓αeq[x;x]       ␈↓is usually true for any ␈↓αx␈↓.
␈↓"∀␈↓ α←␈↓We␈αare␈α␈↓¬not␈↓␈αchanging␈αthe␈αdefinition␈αof␈α␈↓αeq␈↓;␈αit␈αis␈αstill␈αundefined␈αfor␈αnon-atomic
␈↓ α←␈↓arguments.␈α The␈αpreceding␈αremarks␈αdeal␈αonly␈αwith␈αthe␈αusual␈αimplementation
␈↓ α←␈↓of ␈↓αeq␈↓.␈↓π 8␈↓
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓␈α⊃The␈α⊃implementation␈α∩of␈α⊃the␈α⊃truth␈α⊃values␈α∩␈↓
t␈↓␈α⊃and␈α⊃␈↓
f␈↓␈α⊃is␈α∩usually␈α⊃simplified,
␈↓ α←␈↓␈↓ β∂mapping␈α␈↓
f␈↓␈αonto␈α␈↓αNIL␈↓,␈αbut␈αallowing␈αanything␈α␈↓¬but␈↓␈α␈↓αNIL␈↓␈αas␈αa␈αrepresentation
␈↓ α←␈↓␈↓ β∂of ␈↓
t␈↓.  This allows several related tricks:
␈↓"	␈↓ α←␈↓␈↓ βK␈↓↓a.␈↓ Any expression may be used as a predicate, and
␈↓"	␈↓ α←␈↓␈↓ βK␈↓↓b.␈↓ Used as a predicate, ␈↓αnot[null[l]]␈↓ has the same effect as ␈↓αl␈↓.

␈↓"β␈↓ α←␈↓For␈α∃example,␈α⊗consider␈α∃the␈α∃following␈α⊗extended␈α∃version␈α∃of␈α⊗the␈α∃predicate
␈↓ α←␈↓␈↓αmember␈↓.
␈↓"∀␈↓ α←␈↓αmem␈↓λ'␈↓α <= λ[[x;l]␈↓ ∧+[null[l] → ␈↓
f␈↓α;
␈↓"β␈↓ α←␈↓α␈↓ ∧+ equal[x;first[l]] → l;
␈↓"β␈↓ α←␈↓α␈↓ ∧+ ␈↓
t␈↓α → mem␈↓λ'␈↓α[x;rest[l]]] ]
␈↓"∀␈↓ α←␈↓␈↓ β'This␈α∞"predicate",␈α
␈↓αmem␈↓λ'␈↓,␈α∞will␈α
return␈α∞␈↓
f␈↓␈α
if␈α∞no␈α
matching␈α∞element␈α∞is␈α
found,
␈↓ α←␈↓otherwise␈α∞it␈α
will␈α∞return␈α
the␈α∞list␈α∞beginning␈α
at␈α∞the␈α
match.␈α∞The␈α∞non-empty␈α
list
␈↓ α←␈↓can␈α∪be␈α∩used␈α∪as␈α∪an␈α∩indication␈α∪of␈α∩truth,␈α∪and␈α∪can␈α∩also␈α∪supply␈α∪the␈α∩calling
␈↓ α←␈↓function with the match if a match is found.

␈↓"β␈↓ α←␈↓________________
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 7␈↓See the problem on hash consing on page 287.
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 8␈↓Formally,␈αthe␈α
implementation␈α␈↓¬is␈↓␈α
wrong␈αin␈α
not␈αsatisfying␈αthe␈α
definition.
␈↓ α←␈↓Pragmatically, the implementation is convenient.
/FONT#0=BASL30/FONT#1=BASB30= -.1235:ADEFPSTabcdeghilmnopqrstuwxyy/FONT#2=ASI30[LSP,JRA]=λ→ ()+.012349:;<=>ABCDEGILMNOPQRSTUVXYZ[]←abcdefghilmnopqrstuvxyz||/FONT#3=SUB=12nn/FONT#5=ASI30[LSP,JRA]=abefilmnoprstuvxx/FONT#7=SUP= 2356788/FONT#8=SPEC[LSP,JRA]=''/FONT#11=METSB= .012345679CEILPSacdefilmnoprstuvxx/FONT#12=NGB30=<>abcejlmnoprstuxx/FONT#13=GERM35=ftt